package com.xxd.algo.newcode.base01.class07;

/**
 * @author: XiaoDong.Xie
 * @create: 2021-01-11 10:39
 * @description:
 */
public class BestArrangeTest2 {

    public static class Program {
        public int start;
        public int end;

        public Program(int start, int end) {
            this.start = start;
            this.end = end;
        }

        @Override
        public String toString() {
            return "Program{" +
                    "start=" + start +
                    ", end=" + end +
                    '}';
        }
    }

    public static int bestArrange(Program[] programs) {
        if (programs == null || programs.length == 0) {
            return 0;
        }
        return process(programs, 0, 0);
    }

    /**
     * 暴力递归的方法
     *
     * @param programs
     * @return
     */
    private static int process(Program[] programs, int done, int timeline) {
        if (programs.length == 0) {
            return 0;
        }
        printParam(programs, done, timeline);

      //  System.out.println(programs + "done " + done + "timeline " + timeline);
        int max = done;
        for (int i = 0; i < programs.length; i++) {
            if (programs[i].start >= timeline) { // 可以安排
                Program[] next = copyButExcept(programs, i);
                max = Math.max(max, process(next, done + 1, programs[i].end));
            }
        }

        return max;
    }

    private static void printParam(Program[] programs, int done, int timeline) {
        for (Program program : programs) {
            System.out.print(program + "\t");
        }
        System.out.println("done " + done + "  timeline " + timeline);
    }

    /**
     * 拷贝除了 i 节点元素的数组
     *
     * @param programs 数组
     * @param i        节点索引
     * @return 新数组
     */
    public static Program[] copyButExcept(Program[] programs, int i) {
        Program[] ans = new Program[programs.length - 1];
        int index = 0;
        for (int k = 0; k < programs.length; k++) {
            if (k != i) {
                ans[index++] = programs[k];
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        Program[] programs = new Program[4];
        programs[0] = new Program(0, 3);
        programs[1] = new Program(0, 5);
        programs[2] = new Program(4, 6);
        programs[3] = new Program(12, 14);
        System.out.println(bestArrange(programs));

    }
}